package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.knowledge.KBackTracking;
import pro.softzhang.algo.flag.theme.TMathPermulation;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 */
@KBackTracking
@TMathPermulation
public class LC47_PermutationsII {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> r = new ArrayList<>();
            doPermuteUnique(nums, 0, r);
            return r;
        }

        private void doPermuteUnique(int[] nums, int i, List<List<Integer>> r) {
            if(i == nums.length) {
                List<Integer> p = new ArrayList<>();
                for (int num : nums) {
                    p.add(num);
                }
                r.add(p);
                return;
            }

            Set<Integer> set = new HashSet<>();
            for (int j = i; j < nums.length; j++) {
                if(set.contains(nums[j])) {
                    continue;
                }

                set.add(nums[j]);
                swap(nums, i, j);
                doPermuteUnique(nums, i + 1, r);
                swap(nums, i, j);
            }
        }

        private void swap(int[] nums, int i, int j) {
            if(i != j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
    }
}
